This invention relates to a parallel multiplier with an operand of number data, and more particularly to a partial-product adder circuit, which is used in a parallel multiplier based on Booth's algorithm.
There have been proposed various types of algorithms for performing the parallel multiplication at a high speed. Some of these proposals are described in "NIKKEI ELECTRONICS", issued May 29, 1978, pp 76 to 89, and "High-Speed Operating of Computers", translated by Horigoe, issued by Kindai Kagaku-sha, pp 129 to 213. In the parallel multiplication based on the Booth's aloorithm described in "NIKKEI ELECTRONICS", to perform multiplication of multiplicand n bit and multiplier n bit (n.times.n bit), the number of the partial-products to be obtained is only n/2. The adder circuit for partial-product used in the 8.times.8 bit multiplier of Booth's algorithm is configured as shown in FIG. 1.
As shown, the multiplier contains three adder rows each made up of 11 full adders FA. In each adder row, the full adders of 9 upper order bits are of the carry save system, while the full adders of 2 lower order bits, are of the ripple carry system. In each adder row, the most significant bit is located on the left side, as viewed in the drawing. The least significant bit is located on the right side. The sum signal produced from each bit full adder in one full adder row is connected with the corresponding bit full adder of the higher order full adder row. In the figure, the uppermost full adder row is the lowest order row, and its significance order becomes higher toward the bottom of the drawing. The carry signal produced from one bit full adder in the lower order full adder row is connected to the bit full adder of the higher full adder row, which is one bit higher than the former bit full adder. The final full adder row is an adder I, based on the carry look ahead (CLA) mode. Such an arrangement needs only (m-1) adder rows, to add together the partial-product signals of m. In this example, the product signals are four, X0 to X3, each consisting of 8 bits. Therefore, it is possible to reduce the chip size and to speed up the operation. These signals X0 to X3 are selected by the output signal from a decoder (not shown) in which five types of partial-products for multiplicand X, -X, 2X, -2X, and 0 (or 1), decode multiple Y on the basis of a predetermined logic formula. The 8-bit data of partial-product signal X0 is input to the lower order 8-bit adder of the lowest order full adder row (the uppermost row in the drawing). The 8-bit data of the partial-product signal X1 is input to the upper order 8-bit adder of the lowest order full adder row. The 8-bit data of the partial-product signal X2 is connected to the upper order 8-bit adder of the full adder row one digit higher than the lowest order full adder row (the second row from the top). The partial-product signal X3 is connected to the upper order 8-bit adder of the full adder row (the third row from the top). The two higher order bit adders of each adder row are coupled with one bit signal SB for code-processing the input partial-products. When the input partial-product is negative (-X or -2X), signals CB0 to CB3 (which are all 1) for generating "2's complement" are input to the least significant bit of the product. Signals CB1 to CB3, except CB0, are input to the least significant bit adder of the adder row one digit higher than the row to which the negative partial-product is applied. Specifically, if X1 is the negative partial-product signal, this signal is applied to the 1 to 8 bit adders of the lowest order row R1. In this case the signal CB1 for the "2's complement" generation is input to the adder of the least significant bit 11 of the other row R2, which is one digit higher than the row R1. In the case that the one digit higher row is a CLA type adder I, the signal CB1 is input to the carry input terminal Cin.
In the conventional partial-product adder circuit, the carry signal is propagated in the two lower order bit adders in the ripple carry mode. Therefore, the time for multiplication is increased by the propagation time. This presents a problem. To solve this problem, if the CLA system is used for the two lower order bit additions in each adder row, the hardware of the circuit is increased and the regularity of the circuit pattern is degraded. In this respect, such an approach is inappropriate for IC fabrication. To keep the pattern regularity, if the carry save system, not the ripple carry system, is applied to all of the other rows, it is necessary to increase the number of bits by the number corresponding to the two lower order bits in the CLA type adder I. For this reason, it is impossible to form a pattern for inputting the "2's complement" generating signal CB3 to the carry signal input terminal Cin of the adder 1.